package com.fanwh.sort.InsertSort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * @program: DataStructure
 * @description: 直接插入排序
 * @author: Fanwh
 * @create: 2020-09-24 12:55
 **/
public class InsertSort {

    public static void insertSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int insertVal = arr[i];//插入数据
            int insertIndex = i-1;//待插入数据的前一个数组下标
            /**说明
             * 1.insertIndex >= 0  保证在给insertVal找插入位置时，不越界
             * 2.insertVal<arr[insertIndex]  插入数据比其前一个数据的值要小
             * 3.arr[insertIndex+1] = arr[insertIndex]  将待插入数据其前一个数据后移
             */
            while (insertIndex >= 0 && insertVal<arr[insertIndex]){
                arr[insertIndex+1] = arr[insertIndex];
                insertIndex--;
            }
            arr[insertIndex+1] = insertVal;
        }
    }

    public static void main(String[] args) {
        /*int[] arr = {34,6,3,4};
        System.out.println("排序前");
        System.out.println(Arrays.toString(arr));
        insertSort(arr);
        System.out.println("排序后");
        System.out.println(Arrays.toString(arr));*/

        //测试

    }
}
